package day1227

import . "gocode/algorithm/utils"

func isSubStructure(a, b *TreeNode) bool {
	if a == nil || b == nil {
		return false
	}
	queue := make([]*TreeNode, 0)
	queue = append(queue, a)
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		if isSub(node, b) {
			return true
		}
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
	return false
}

func isSub(a, b *TreeNode) bool {
	if b == nil {
		return true
	}
	if a == nil {
		return false
	}
	if a.Val != b.Val {
		return false
	}
	return isSub(a.Left, b.Left) && isSub(a.Right, b.Right)
}
